An integer program can be used to model a resource allocation problem in which variables are assigned discrete values. A linear integer program expresses a particular resource allocation problem as a set of linear equations or inequalities. A method of solving a linear integer program employs a local search solution. The local search solution uses a gradient following approach to iteratively improve an initial assignment of values to the variables until a near optimal solution is reached. Each iteration of the local search solution produces a new assignment of values for the variables. Generally, the new assignment of values differs from a previous assignment of values by one value for a particular variable. For the linear integer program, a selection of the variables that follows the gradient is accomplished by evaluating coefficients for the variables in an unsatisfied constraint.
In a traditional integer program, the resource allocation problem is expressed in terms of constraints and an objective. The constraints are equations or inequalities. The objective is an optimization function.
Walser, in U.S. Pat. No. 6,031,984, issued on Feb. 29, 2000, teaches a method of solving a linear integer program using a local search solution technique referred to as a WSAT(OIP) method. A linear program model for the WSAT(OIP) method defines the linear integer program as an overconstrained integer program, where hard constraints correspond to the constraints of the traditional integer program and where a sum of soft constraints corresponds to the objective. The WSAT(OIP) method selects the variables that follow the gradient by evaluating the coefficients for the variables in the unsatisfied constraint.
If the integer program includes polynomial terms of second or higher order (i.e., quadratic or higher order terms), the representation of coefficients of the variables as used in the WSAT(OIP) method are insufficient for an indication of the gradient.
A distributed application includes a plurality of services. Each of the services performs a task or tasks as part of the distributed application. Often the distributed application is placed on a network of computers. The network of computers forms a distributed resource infrastructure where each of the computers forms a node. Performance of the distributed application depends on optimizing a placement of the services onto the nodes.
An existing method uses parameters for individual nodes to determine a placement of the services onto the nodes. Such parameters include processing and storage capabilities of the nodes. Services are placed onto the nodes so that processing and storage requirements of the services on a particular node do not exceed the processing and storage capabilities of the node.
The existing method does not consider relationships among the nodes or among the services in the determination of the placement of the services onto the nodes. Another existing method considers topologies between the services and between the nodes but requires that the topologies be fixed in certain configurations. The other existing method does not determine a placement of the services onto the nodes where an arbitrary topology exists between the nodes or between the services.